1. Field
The present invention relates generally to compilers and debuggers and, more specifically, to data value recovery in dynamic runtime systems.
2. Description
Increasing the execution speed of a program has always been a goal of a dynamic runtime system (DRS) such as a dynamic binary translation system and a debugging system of optimized programs. To achieve this goal, a DRS usually employs aggressive optimization techniques, e.g., global optimizations, and reordering, insertion and deletion of instructions. These optimization techniques may move instructions around to achieve a higher execution speed. As a result, the execution order of instructions after optimizations may be different from the execution order of instructions before the optimizations. For example, instruction A is executed before instruction B before optimizations; but instruction A may be executed after instruction B after the optimizations. A different execution order resulting from the optimizations may cause problems in recovering originally expected data values (before optimizations) for some variables at certain exception points. In other words, the actual value of a variable might not be the originally expected value of the variable at an exception point. Such problems may be further complicated by branches in a program. The execution order may change due to optimizations for one side of a binary branch, but not for the other side. An exception point where data values of all variables can be correctly determined as originally expected is called precise exception. It is important to achieve precise exceptions so that bugs causing exceptions can be correctly identified. Precise exceptions can usually be achieved through the information of an execution path leading to the exception point at execution time. Similarly, it is also important to recover the expected values of data at each break point during a debugging process.
One solution to determine an execution path is to instrument each block (a set of codes) to dump a timestamp each time the block is executed as proposed by D. M. Dhamdhere and K. V. Sankaranarayanan in “Dynamic Currency Determination in Optimized Programs,” published in Association for Computing Machinery (ACM) Transactions on Programming Languages and Systems, vol. 20, 1998, pages 1111-30. A program may be divided into blocks according to branch instructions. This solution, however, leads to a 10-20 percent slowdown of an optimized program. Another solution is to increment a register along a subset of the execution edges to encode the current execution path, as described by T. Ball and J. Larus in “Efficient Path Profiling,” published in Proceedings of 29th Annual IEEE/ACM International Symposium on Microarchitecture, 1996. However, this solution is for static path profiling and may slow down the optimized program by about 40 percent. Therefore, a new solution that does not incur much overhead and can dynamically profile the execution path to ensure data value recovery is desired.